package com.leetcode.partition2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/24 10:37
 */
public class LC119杨辉三角2 {

    /**
     * 获取杨辉三角的指定行
     * 使用组合公式C(n,i) = n!/(i!*(n-i)!)
     * 则第(i+1)项是第i项的倍数=(n-i)/(i+1);
     */
    public static List<Integer> getRow(int rowIndex) {
        return dynamicProgramming(rowIndex);
    }

    private static List<Integer> dynamicProgramming(int rowIndex) {
        if (rowIndex == 0) return Collections.singletonList(1);
        List<Integer> prevLevel = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {         //遍历层
            List<Integer> currentLevel = new ArrayList<>();
            currentLevel.add(1);                    //当前层的第一列为1
            for (int j = 1; j < i; j++) {          //遍历该层的列
                int val = prevLevel.get(j - 1) + prevLevel.get(j);
                currentLevel.add(val);
            }
            currentLevel.add(1);                    //当前层的最后一列为1
            prevLevel = currentLevel;
        }
        return prevLevel;
    }

    private static List<Integer> mathSolution(int rowIndex) {
        List<Integer> answer = new ArrayList<>(rowIndex + 1);
        long cur = 1;
        for (int i = 0; i <= rowIndex; i++) {
            answer.add((int) cur);
            cur = cur * (rowIndex - 1) / (i + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(getRow(4));
    }
}
